#include <malloc.h>
#include <memory.h>
#include <stdint.h>
#include <stdlib.h>

// 倒序
static int32_t _cmp_int(const void* left_p, const void* right_p) {
	return *(int32_t*)right_p - *(int32_t*)left_p;
}

// 二分查找第一个（相乘后）小于者
static uint32_t _find_first_less(long long target, uint32_t mul,
				 const int32_t sorted_potion_b[],
				 uint32_t potion_nums) {
	const int32_t* start_p = sorted_potion_b;
	uint32_t len = potion_nums;
	while (len > 1) {
		uint32_t right_len = (len >> 1);
		uint32_t left_len = len - right_len;
		uint32_t value = start_p[left_len - 1];
		long long mul_result = (long long)value * (long long)mul;
		if (mul_result < target) {
			len = left_len;
		} else {
			start_p += left_len;
			len = right_len;
		}
	}
	return start_p - sorted_potion_b;
}

int32_t* _get_result(const int32_t spell_b[], uint32_t spell_nums,
		     const int32_t sorted_potion_b[], uint32_t potion_nums,
		     long long success) {
	int32_t* result_b = malloc(sizeof(int32_t[spell_nums]));
	for (uint32_t i = 0; i < spell_nums; i++) {
		result_b[i] = _find_first_less(
			success, spell_b[i], sorted_potion_b, potion_nums + 1);
	}
	return result_b;
}

int* successfulPairs(int spell_b[], int spell_nums, int potion_b[],
		     int potion_nums, long long success, int* return_nums_p) {
	int32_t* sorted_potion_b = malloc(sizeof(int32_t[potion_nums]));
	memcpy(sorted_potion_b, potion_b, sizeof(int32_t[potion_nums]));
	qsort(sorted_potion_b, potion_nums, sizeof(int32_t), _cmp_int);
	int32_t* result_p = _get_result(spell_b, spell_nums, sorted_potion_b,
					potion_nums, success);
	free(sorted_potion_b);
	*return_nums_p = spell_nums;
	return result_p;
}
